# Count.py
'''
我们的实现包括三个数据结构: 一个Count Sketch, 一个小顶堆和一个字典, 其中小顶堆用于
找出具有最小计数值的数据流, 字典用于数据流的存在性检查. Count Sketch占用了一半的内
存空间, 小顶堆和字典分别占用1/4的内存空间.
作者：赵宗义，xinshengzzy@foxmail.com
'''
from simulators.BaseSimulator import BaseSimulator
import mytools
import my_constants as mc
import 文件工具箱
from 数学工具 import 求中位数
import heapq


class Count(BaseSimulator):
    def __init__(self, 内存=1.0):
        super(Count, self).__init__()
        tmp = int(0.5*内存*1024.0*1024.0/(4*4))  # 假设这个sketch共有四行
        self.表长1 = tmp
        self.表长2 = tmp
        self.表长3 = tmp
        self.表长4 = tmp
        self.哈希表 = [0]*(self.表长1 + self.表长2 + self.表长3 + self.表长4)
        self.容量 = int(0.25*内存*1024.0*1024.0/17)
        self.流记录集 = dict()
        self.小顶堆 = []

    def 创建数据结构(self):
        self.哈希表 = [0]*(self.表长1 + self.表长2 + self.表长3 + self.表长4)

    def 配置内存方案(self, 内存方案):
        mc.配置内存方案(内存方案)

    def 处理数据包(self, 标识符, 时间戳):
        '''处理一个新到达的数据包'''
        偏移量 = [0]
        for 表长 in [self.表长1, self.表长2, self.表长3]:
            偏移量.append(偏移量[-1] + 表长)
        索引1 = mytools.hash1(标识符.encode('utf-8')) % self.表长1 + 偏移量[0]
        索引2 = mytools.hash2(标识符.encode('utf-8')) % self.表长2 + 偏移量[1]
        索引3 = mytools.hash3(标识符.encode('utf-8')) % self.表长3 + 偏移量[2]
        索引4 = mytools.hash4(标识符.encode('utf-8')) % self.表长4 + 偏移量[3]
        tmp = [-1, 1]
        s1 = tmp[mytools.hash5(标识符.encode('utf-8')) % 2]
        s2 = tmp[mytools.hash6(标识符.encode('utf-8')) % 2]
        s3 = tmp[mytools.hash7(标识符.encode('utf-8')) % 2]
        s4 = tmp[mytools.hash8(标识符.encode('utf-8')) % 2]
        计数值 = []
        for 索引, 增量 in zip([索引1, 索引2, 索引3, 索引4], [s1, s2, s3, s4]):
            self.哈希表[索引] += 增量
            计数值.append(self.哈希表[索引]*增量)
        流长度 = 求中位数(计数值)
        if 标识符 in self.流记录集:
            self.流记录集[标识符] += 1
        elif len(self.流记录集) < self.容量:
            self.流记录集[标识符] = 流长度
            heapq.heappush(self.小顶堆, (流长度, 标识符))
        else:  # 我们要考虑替换流记录集中的数据流了
            self.更新流记录集(标识符, 流长度)

    def 更新流记录集(self, 标识符, 流长度):
        # 计数器 = 0
        while True:
            # print("小顶堆长度:%d, 计数器:%d" % (len(self.小顶堆), 计数器))
            # 计数器 += 1
            临流长度, 临标识符 = heapq.heappop(self.小顶堆)
            assert(临流长度 <= self.流记录集[临标识符])
            if 临流长度 < self.流记录集[临标识符]:
                heapq.heappush(self.小顶堆, (self.流记录集[临标识符], 临标识符))
            else:  # 临流长度 == self.流记录集[临标识符]
                if 临流长度 >= 流长度:
                    heapq.heappush(self.小顶堆, (self.流记录集[临标识符], 临标识符))
                    break
                else:
                    del self.流记录集[临标识符]
                    self.流记录集[标识符] = 流长度
                    heapq.heappush(self.小顶堆, (流长度, 标识符))
                    break

    def 备份(self, 文件名):
        备份 = dict()
        备份["流记录集"] = self.流记录集
        文件工具箱.备份数据结构(备份, 文件名)
